package com.bupt.leetcode;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Map;

import com.bupt.datastruct.*;
import com.bupt.datastruct.ListNode;
import com.bupt.datastruct.RandomListNode;
public class LinkedListProblem {
	
	/**
	 * 根据数组构造链表
	 * @param arr
	 * @return
	 */
	public ListNode constructLinkedList(int[] arr){
		if(arr.length == 0) return null;
		ListNode head = null,tail = null;
		for(int i = 0 ;i<arr.length ;i++){
			ListNode node = new ListNode(arr[i]);
			if(head == null) head = node;
			if(tail != null){
				tail.next = node;
			}
			tail = node;
		}
		return head;
	}
	/**
	 * 输出链表
	 * @param head
	 * @return
	 */
	public String outputLinkedList(ListNode head){
		StringBuilder sb = new StringBuilder("[");
		while(head != null){
			sb.append(head.val);
			if(head.next != null) {
				sb.append(",");
			}
			head = head.next;
		}
		sb.append("]");
		return sb.toString();
	}
	/**
	 * 题号： url :https://leetcode.com/problems/swap-nodes-in-pairs/ 交换链表邻接元素
	 * @param head
	 * @return
	 */
	public ListNode swapPairs(ListNode head) {
		ListNode p = head, pre = null;
		while (p != null && p.next != null) {
			ListNode pNext = p.next;
			p.next = pNext.next;
			pNext.next = p;
			if (pre == null) {
				head = pNext;
			} else {
				pre.next = pNext;
			}
			pre = p;
			p = p.next;
		}
		return head;
	}
	/**
	 * 旋转链表
	 * @param head
	 * @param k
	 * @return
	 */
	public ListNode rotateRight(ListNode head, int k) {
		if (head == null || head.next == null)
			return head;
		int len = 0;
		ListNode p = head, tail = null, fast = head, pre = null;
		while (p != null) {
			tail = p;
			p = p.next;
			len++;
		}
		k = k % len;
		if (k == 0)
			return head;
		while (k-- > 0)
			fast = fast.next;
		p = head;
		while (fast != null) {
			pre = p;
			p = p.next;
			fast = fast.next;
		}
		tail.next = head;
		pre.next = null;
		return p;
	}
	/**
	 * 删除链表中等于
	 * @param head
	 * @param val
	 * @return
	 */
	public ListNode removeElements(ListNode head, int val) {
		if (head == null)
			return head;
		ListNode p = head, pre = null;
		while (p != null) {
			if (p.val == val) {
				if (pre == null) {
					head = p.next;
				} else {
					pre.next = p.next;
				}
			} else {
				pre = p;
			}
			p = p.next;
		}
		return head;
	}
	/**
	 * 合并n个排序链表
	 * @param lists
	 * @return
	 */
    public ListNode mergeKLists(ListNode[] lists) {
    	if(lists == null || lists.length == 0 ) return null;
    	if(lists.length == 1) return lists[0];
    	LinkedList<ListNode> stack1  = new LinkedList<ListNode>();
    	LinkedList<ListNode> stack2  = new LinkedList<ListNode>();
    	for(int i = 0; i< lists.length;i++){
    		if(lists[i] != null) {
    			stack1.push(lists[i]);
    		}
    	}
    	while(stack1.size() > 1 || stack2.size() > 1){
    		while(!stack1.isEmpty()){
    			ListNode node1 = stack1.size() >0 ? stack1.pop() : null;
    			ListNode node2 = stack1.size() >0 ? stack1.pop() : null;
    			stack2.push(mergeTwoLists(node1, node2));
    		}
    		while(!stack2.isEmpty()){
    			ListNode node1 = stack2.size() >0 ? stack2.pop() : null;
    			ListNode node2 = stack2.size() >0 ? stack2.pop() : null;
    			stack1.push(mergeTwoLists(node1, node2));
    		}
    	}
    	if(stack1.size() > 0){
    		return stack1.peek();
    	}else {
    		return stack2.peek();
    	}
    }
    /**
     * url :https://leetcode.com/problems/remove-nth-node-from-end-of-list/
     * 题号 ：19 
     * 删除倒数第n个节点
     * @param head
     * @param n
     * @return
     */
    public ListNode removeNthFromEnd(ListNode head, int n) {
        if(head == null) return null;
        ListNode fast = head,p = head ,pre = null;
        while(--n > 0 && fast != null){
        	fast = fast.next;
        }
        while(fast != null){
        	pre = p;
        	p = p.next;
        	fast = fast.next;
        }
        if(pre == null) {
        	head = head.next;
        }else {
        	pre.next = p.next;
        }
        return head;
    }

	/**
	 * 合并排序链表
	 * 
	 * @param l1
	 * @param l2
	 * @return
	 */
	public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
		if (l1 == null)
			return l2;
		if (l2 == null)
			return l1;
		ListNode p1 = l1, p2 = l2, head = null, p = null;
		while (p1 != null && p2 != null) {
			ListNode cur = null;
			if (p1.val < p2.val) {
				cur = p1;
				p1 = p1.next;
			} else {
				cur = p2;
				p2 = p2.next;
			}
			if (p == null) {
				head = cur;
				p = head;
			} else {
				p.next = cur;
				p = cur;
			}
		}
		if (p1 != null)
			p.next = p1;
		else {
			p.next = p2;
		}
		return head;
	}
	/**
	 * 翻转某两个节点之间的链表
	 * @param head
	 * @param m
	 * @param n
	 * @return
	 */
	public ListNode reverseBetween(ListNode head, int m, int n) {
        if(head == null || head.next == null)  return head;
        if(m < 1 || n - m < 1) return head;
        ListNode pre = null,p = head,rPre = null,rStart = null;
        while(--m > 0){
        	pre = p;
        	p = p.next;
        	n--; 
        }
        rStart = p;
        while(n-- >0){
        	ListNode pNext = p.next;
        	p.next = rPre;
        	rPre = p;
        	p = pNext;
        }
        if(pre == null){
        	head = rPre;
        }else {
        	pre.next = rPre;
        }
        rStart.next = p;
        return head;
    }
	/**
	 * 链表分块
	 * @param head
	 * @param x
	 * @return
	 */
    public ListNode partition(ListNode head, int x) {
    	if(head == null) return head;
        ListNode p = head,post = null,pre = null,preTail = null,postTail = null;
        while(p != null){
        	if(p.val < x){
        		if(preTail == null){
        			pre = p;
        		}else {
        			preTail.next = p;
        		}
    			preTail = p;
        	}else {
        		if(postTail == null){
        			post = p;
        		}else {
        			postTail.next = p;
        		}
        		postTail = p;
        	}
        	p = p.next;
        }
        if(postTail!= null) postTail.next = null;
        if(pre == null){
        	return post;
        } else {
        	preTail.next = post;
        	return pre;
        }
    }
    /**
     * 删除链表重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicatesI(ListNode head) {
    	if(head == null || head.next == null) return head; 
        HashSet<Integer> set = new HashSet<Integer>();
        ListNode p = head,pre = null;
        while(p!= null){
        	if(!set.contains(p.val)){
        		set.add(p.val);
        		pre = p;
        	}else {
        		pre.next = p.next;
        	}
        	p = p.next;
        }
        return head;
    }
    /**
<<<<<<< HEAD
     * 题号：25 
     * url :https://leetcode.com/problems/reverse-nodes-in-k-group/ 
     * Reverse Nodes in k-Group 
     * @param head
     * @param k
     * @return
     */
    public ListNode reverseKGroup(ListNode head, int k) {
        if(k <= 1 || head == null || head.next == null) return head;
        ListNode kTail = null,pre = null, p =head,temp = null,kTailPre = null;
        int step = 0;
        while(p != null) {
        	step = k;
        	kTail = p;
        	pre = null;
        	while(step > 0 && p != null){
        		temp = p.next;
        		p.next = pre;
        		pre = p;
        		p = temp;
        		step--;
        	}
        	if(step == 0){
        		if(kTailPre == null){
        			head = pre;
        		}else {
        			kTailPre.next = pre;
        		}
        		kTailPre = kTail;
        	}
        }
        if(step > 0) {
        	p = pre;
        	pre = null;
        	while(step < k && p != null){
        		temp = p.next;
        		p.next = pre;
        		pre = p;
        		p = temp;
        		step++;
        	}
        	if(kTailPre == null) {
        		head = pre;
        	}else {
        		kTailPre.next = pre;
        	}
        }
        return head;
    }
    /**
     * 题号：2
     * url : https://leetcode.com/problems/add-two-numbers/
     * @param l1
     * @param l2
     * @return
     */
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        if(l1 == null) return l2;
        if(l2 == null) return l1;
        ListNode p1 = l1, p2 = l2,head = p1,pre = null;
        int lowDigit = 0;
        while(p1 != null && p2 != null){
        	int d = p1.val + p2.val + lowDigit;
        	lowDigit = d > 9 ? 1:0;
        	p1.val = d%10;
        	pre = p1;
        	p1 = p1.next;
        	p2 = p2.next;
        }
        if( p1 != null && p2 == null){
        	while(lowDigit > 0 && p1 != null){
        		int d = lowDigit + p1.val;
        		lowDigit = d > 9 ? 1:0;
        		p1.val = d % 10;
        		pre.next = p1;
        		pre = p1;
        		p1 = p1.next;
        	} 
        }else if(p2 != null && p1 == null){
        	while(p2 != null && lowDigit > 0){
        		int d = lowDigit + p2.val;
        		lowDigit = d > 9 ? 1:0;
        		p2.val = d % 10;
        		pre.next = p2;
        		pre = p2;
        		p2 = p2.next;
        	}
        }
        if(lowDigit > 0 ){
        	l2.val = 1;
        	l2.next = null;
        	pre.next = l2;
        }
        return head;
    }
    /**
     * 链表是否有环
     * @param head
     * @return
     */
    public boolean hasCycle(ListNode head) {
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
        	fast = fast.next.next;
        	slow = slow.next;
        	if(fast == slow) return true;
        }
        return false;
    }
    /**
     * 链表环入口
     * @param head
     * @return
     */
    public ListNode CycleJoin(ListNode head){
        ListNode fast = head, slow = head;
        while(fast != null && fast.next != null){
        	fast = fast.next.next;
        	slow = slow.next;
        	if(fast == slow) break;
        }
        if(fast == null || fast.next == null) return null;
    	slow = head;
    	while(fast != slow){
    		fast = fast.next;
    		slow = slow.next;
    	}
    	return fast;
    }
    /**
     * 链表交点,双指针同时遍历，如果pa到链表尾，pa指向headB,类似，pb到链表尾，pb指向headA
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode1(ListNode headA, ListNode headB) {
    	ListNode pa = headA,pb = headB;
    	while(pa != pb ){
    		pa = pa == null ? headB:pa.next;
    		pb = pb == null ? headA:pb.next;
    	}
    	return pa;
    }
    /**
     * 链表交点，解题思路2 长链表先走|lenA - lenB|
     * @param headA
     * @param headB
     * @return
     */
    public ListNode getIntersectionNode2(ListNode headA, ListNode headB) {
    	ListNode pa = headA,pb = headB;
    	while(pa != null && pb != null){
    		pa = pa.next;
    		pb = pb.next;
    	}
    	ListNode p = pa == null ? pb : pa;
    	int len = 0;
    	while(p != null) p = p.next;
    	p = pa == null ? headB:headA;
    	while(len-- > 0) p = p.next;
    	if(pa == null){
    		pb = p;
    	}else {
    		pa = p;
    	}
    	while(pa != pb){
    		pa = pa.next;
    		pb = pb.next;
    	}
    	return pa;
    }
    /**
     * 
     * @param head
     * @return
     */
    public RandomListNode copyRandomList(RandomListNode head) {
       if(head == null) return head;
       RandomListNode p = head, random = p;
       while(p != null){
    	   RandomListNode node = new RandomListNode(p.label);
    	   node.next = p.next;
    	   p.next = node;
    	   p = node.next;
       }
       p = head;
       while(p != null){
    	   if(p.random != null){
    		   p.next.random = p.random.next;
    	   }else {
    		   p.next.random = null;
    	   }
    	   p = p.next.next;
       }
       p = head;
       random = p.next;
       RandomListNode copy = p.next;
       while(p != null){
    	   p.next = p.next.next;
    	   copy.next = p.next == null ? null : p.next.next;
    	   p = p.next;
    	   copy = copy.next;
       }
       return random;
    }
     /**
     * 就地逆置链表
     * @param head
     * @return
     */
    public ListNode reverseList(ListNode head) {
        if(head == null || head.next == null) return head;
        ListNode p = head,pre = null;
        while(p != null){
        	ListNode temp = p.next;
        	p.next = pre;
        	pre = p;
        	p = temp;
        }
        return pre;
    }
    /**
     * 删除链表内所有重复元素
     * @param head
     * @return
     */
    public ListNode deleteDuplicatesII(ListNode head) {
    	if(head == null || head.next == null) return head; 
    	HashSet<Integer> set1 = new HashSet<Integer>();
    	HashSet<Integer> set2 = new HashSet<Integer>();
        ListNode p = head,pre = null;
        while(p!= null){
        	if(!set1.contains(p.val)){
        		set1.add(p.val);
        		pre = p;
        	}else {
        		set2.add(p.val);
        		pre.next = p.next;
        	}
        	p = p.next;
        }
        pre = null;
        p = head;
        while(p != null){
        	if(!set2.contains(p.val)){
        		pre = p;
        	}else {
        		if(pre != null){
        			pre.next = p.next;
        		}else {
        			head = p.next;
        		}
        	}
        	p = p.next;
        }
        return head;
    }

}
